1. Field of the Invention
This invention relates to a method and a system for controlling mutually exclusive resources that are available sequentially in an event driven process. The sequentially available resources are controlled by a computer, a programmable logic controller or the like.
2. Description of the Prior Art
Important concepts in the recent computer technology art are multitasking, multiprocessing and distributed processing. To implement these techniques, it is necessary to share a resource between several tasks or processes during parallel execution of a plurality of tasks or processes. Such a resource is called a shared resource, for example, various peripheral devices, disks, memories, communication lines, programs, and data. A shared resource that can be appropriated by one task or process at a time is called a critical resource.
The problem of controlling mutually exclusive resources in an event driven process arises when event driven processes are executed in parallel and compete for the shared resource. The mutually exclusive resource control mechanism assures that the shared resource will be held by at most one process. An area which holds a shared resource in the processes executed in parallel is called a critical section. The problem of sharing a resource when a plurality of tasks are executed in parallel is presented as a problem of interprocess communication and synchronization. To solve it conventionally, various techniques have been proposed, and analyzed by system models. The synchronization problem includes the mutual exclusion problem, the producer consumer problem, the dining philosopher problem, and the reader/writer problem.
At present, there is no way to solve the problem of automatically controlling access to a mutually exclusive resource among a plurality of competing processes. It is a burden for the programmer or the operator. Thus, whether a programmer writes a program executing in parallel, or an operator executes a program under such an environment, attention must always be paid to resource assignment. In implementing a parallel execution system, a programmer uses semaphores to control access.
An example of programming using semaphores will be explained as follows. It is assumed that there are three flows of event driven processes G.sub.1, G.sub.2 and G.sub.3 as shown schematically in FIG. 2. In the first flow of process G.sub.1, tasks p.sub.1 and p.sub.2 are processed sequentially. After the task p.sub.1 has been executed while using shared resources A and C, the task p.sub.2 is executed while using shared resources B and C.
In the second flow of process G.sub.2, a task P.sub.3 is executed. The task P.sub.3 is executed while using the shared resources A, B and C. In the third flow of process G.sub.3, tasks P.sub.4 and P.sub.5 are executed in parallel. The task P.sub.4 is executed while using the shared resources A and C, and the task P.sub.5 is simultaneously executed while using the shared resources B and C. The start or end points of the tasks are indicated by time marks t.sub.1 --t.sub.7. It is assumed that, among the resources appearing in FIG. 2, the critical resources are A and B, and that the critical resource A is a robot 2, while the critical resource B is a robot 1.
At present, in most cases, software programming is performed for each critical resource, i.e., a controller for production apparatus in a manufacturing process, or a computer in a network system. This requires a program for each critical resource and a program for controlling them. An example of this is shown in FIGS. 3A-3C. FIG. 3A is a program for controlling the entire system; FIG. 3B is a program for controlling the robot 1; FIG. 3C is a program for controlling the robot 2.
The syntax for describing the parallel execution is as follows: ##STR1## wherein P1 and P2 are tasks executed in parallel.
In addition, syntax for describing a critical section is as follows: ##STR2## wherein R is a unique name for a critical resource to be mutually excluded, and S is a critical section to be mutually excluded. In this case, R is a semaphore.
In FIG. 3A, R(p) is a program for a robot as indicated in FIGS. 3B and 3C, respectively. When a parameter p is passed to R, the program for R executes only the task for p.
The syntax for describing the critical section and its mechanism, as well as the syntax for describing the parallel execution and its mechanism are not supplied to the programmer generally, so that it becomes the responsibility of the programmer to write the description of the critical section, to produce its mechanism, and to debug the process for mutually exclusive control.
One technique that is widely used for modeling of a system is called a Petri-Net. Features of the Petri-Net are parallelism or simultaneousness and nonsynchronization. Its execution may be considered to be a series of discrete events with the timing when an event occurs being indefinite. Attempts have been made to utilize these features and the execution form for event driven control. The Petri-Net is useful in the simulation of a parallel execution system such as a computer model or a manufacturing process because of its mathematical analysis characteristics and modeling capabilities.
The Petri-Net consists of four components: a place, a transition, an arc, and a token. The place indicates an event, the transition indicates a condition, the arc indicates a path, and the token indicates a state. The token moves in the arc between the places according to the condition of the transition, and causes an event corresponding to the place.
FIG. 4 shows examples illustrating the execution of the Petri Net. In this example, the Petri Net is described by using a transition T={t.sub.a, t.sub.b, t.sub.c }, a place P={P.sub.x, P.sub.y, P.sub.z }, and a token. First, if there is no token in P.sub.x, t.sub.a generates a token and places it in P.sub.x (FIG. 4A). If P.sub.x has a token, and P.sub.y and P.sub.z do not have a token, t.sub.b transfers the token to P.sub.y and P.sub.z (FIG. 4B). If P.sub.y and P.sub.z have a token, t.sub.c takes out and erases the token. More details on the Petri Net can be found in "Petri Net Theory and the Modeling of Systems" by J. L. Peterson, Prentice-Hall Inc., 1981.
In a conventional control system using Petri Nets, a programmer describes a flow of processes as shown in FIG. 2 or FIG. 4 by using a graphics editor and then converting the description into code to create a program for controlling the entire system so that, when starting a task or receiving a termination signal, the token is automatically transferred according to these signals based on the program in execution. Description of this system can be found in a paper authored by K. Hasegawa and K. Takahashi, "MFG (Mark Flow Graph)-Based Programmable Controller and its Application to FMS," published in the Proceedings of the International Conference on System Engineering, pp. 306-311, 1984.
However, the conventional control systems do not take the mutually exclusive control problem into consideration. Modeling of the mutually exclusive control problem is performed by creating a place corresponding to an empty state of a resource (empty place) and by connecting it to a place of a task using that resource to establish a critical section. In this case, it utilizes storability which is an important characteristic of the Petri-Net. The empty place contains a token as an initial marking, and always contains a token when a resource is not used. When a process is in a critical section and is using a resource, the empty place does not contain a token. If another process attempts to enter the critical section to use the same resource, it cannot be executed because the empty place does not contain a token and a firing condition is not satisfied. The execution of this other process is forced to wait until the process using the resource ends, releases the resource, and returns the token to the empty place.
FIG. 5 shows an example of this modeling. Place m indicates authorization to enter a critical section. When a process wants to enter the critical section, it supplies a token to p.sub.1 or p.sub.2 to indicate its readiness to enter the critical section, and waits for a signal allowing entrance into the critical section or the token of m to access the critical section. If both processes want to enter the critical section simultaneously, transitions t.sub.1 and t.sub.2 cause contention, and only one process can be fired. Firing of t.sub.1 disables that of t.sub.2, and the process 2 is delayed until the process 1 completes the critical section and returns the token to m.
A control system for providing mutually exclusive control cannot be implemented easily if a graph having empty places for critical resources is created, and converted into codes so as to create a control program for the entire system with the token being automatically transferred. The reasons for this are as follows:
1. The empty places must be incorporated in the Petri-Net. If a programmer incorporates the empty places in a suitable location in the Petri Net while paying attention to critical resources, his effort will be equivalent to programming using semaphores. The creation of the Petri Net becomes very difficult for even a slightly complicated case as illustrated in FIG. 6 as compared with a simple case as illustrated in FIG. 5. PA0 2. In execution, a user must first distinguish the empty places (resource places) from task places, and then place initial tokens in all empty places. This imposes a significant burden on the user. PA0 3. A deadlock may be caused from the representation of the Petri Net itself.
This can be further explained by taking the situation in FIG. 6 as an example. It is assumed that the current state is as shown in FIG. 6A. That is, the tasks P.sub.1 and P.sub.4 are being executed, and the resources P.sub.x and P.sub.y are empty. The resource P.sub.x is used by the tasks P.sub.2, P.sub.3 and P.sub.6. The resource P.sub.y is used by the tasks P.sub.3, P.sub.5 and P.sub.6.
If the state is as shown in FIG. 6A, then it is clear that the control system can start the execution of the tasks P.sub.2 and P.sub.5. Thus, t.sub.1 and t.sub.4 transfer the tokens to P.sub.2 and P.sub.5, respectively. Here, it should be noted that, because the representation as shown in FIG. 5 or FIG. 6 connects each end of the critical section to the empty place of the resource, the token is never transferred to the empty place of P.sub.x until the execution of the task P.sub.3 following the task P.sub.2 is completed, and that, similarly, the token is never transferred to the empty place of P.sub.y until the execution of the task P.sub.6 following the task P.sub.5 is completed. FIG. 6B shows the positions of the tokens after starting the execution of the tasks P.sub.2 and P.sub.5. Now, the control system cannot start the execution of the task P.sub.3 even if the execution of the task P.sub.2 is completed because there is no token in the empty place of P.sub.y. A token is never returned to the empty place of P.sub.x unless the execution of the task P.sub.3 is started. Thus, the execution of the task P.sub.6 is not started either. In this way, the transitions t.sub.2 and t.sub.5 cannot fire and thus cause a deadlock. In the Petri Net, whenever transitions cannot fire, a deadlock results.
In a mathematical representation, G=(P, T, O) where G is the Petri Net structure, P={P.sub.1, P.sub.2, . . . P.sub.M } is a set of places with M&gt;0, and T={T.sub.1, T.sub.2, . . . T.sub.L } is a set of transitions with L&gt;1. The set of places and the set of transitions are disjoint, and P.andgate.T=.PHI.. I: P-&gt;T is an input function from a place to a transition. O: T-&gt;P is an output function from a transition to a place. A Petri Net structure to which is added a marking .mu. for assignment of a token to a place is called a marked Petri-Net. The token exists only in the place, and firing of the transition controls execution. Firing of the transition transfers a token from an input place to an output place. The Petri Net structure is dual in the graph theory. The concept of the dual of a graph is not utilized in the marked Petri-Net because the dual of a graph is difficult to define.